#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"


void QueueInit(Queue* ptr)
{
	assert(ptr);
	//QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//if (newnode == NULL)
	//{
	//	perror("malloc error");
	//	exit(-1);
	//}
	ptr->head = NULL;
	ptr->tail = NULL;
}

void QueueDestroy(Queue* ptr)
{
	assert(ptr);

	QNode* cur = ptr->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ptr->head = ptr->tail = NULL;
}

void QueuePush(Queue* ptr, Datatype x)
{
	assert(ptr);
	QNode* new = (QNode*)malloc(sizeof(QNode));
	if (new == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	new->next = NULL;
	new->val = x;

	if (QueueEmpty(ptr))
	{
		ptr->head = ptr->tail = new;
	}
	else
	{
		ptr->tail->next = new;
		ptr->tail = new;
	}
}

void QueuePop(Queue* ptr)
{
	assert(ptr);
	assert(!QueueEmpty(ptr));

	QNode* next = ptr->head->next;
	free(ptr->head);
	ptr->head = next;
	if (QueueEmpty(ptr))
	{
		ptr->tail = NULL;
	}
}

Datatype QueueFront(Queue* ptr)
{
	assert(ptr);
	assert(!QueueEmpty(ptr));
	return ptr->head->val;
}

Datatype QueueBack(Queue* ptr)
{
	assert(ptr);
	assert(!QueueEmpty(ptr));
	return ptr->tail->val;
}

int QueueSize(Queue* ptr)
{
	assert(ptr);
	
	QNode* cur = ptr->head;
	int size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

bool QueueEmpty(Queue* ptr)
{
	assert(ptr);
	return ptr->head == NULL;
}


MyStack* myStackCreate() {
	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
	if (obj == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	QueueInit(&obj->p1);
	QueueInit(&obj->p2);
	return obj;
}

void myStackPush(MyStack* obj, int x) {
	Queue* empty = &obj->p1;
	Queue* nonempty = &obj->p2;
	if (!QueueEmpty(&obj->p1))
	{
		empty = &obj->p2;
		nonempty = &obj->p1;
	}

	QueuePush(nonempty, x);
}

int myStackPop(MyStack* obj) {
	Queue* empty = &obj->p1;
	Queue* nonempty = &obj->p2;
	if (!QueueEmpty(&obj->p1))
	{
		empty = &obj->p2;
		nonempty = &obj->p1;
	}


	while (nonempty->head->next)
	{
		QueuePush(empty, QueueFront(nonempty));
		QueuePop(nonempty);
	}

	int ret = nonempty->head->val;
	QueuePop(nonempty);
	return ret;
}

int myStackTop(MyStack* obj) {
	Queue* empty = &obj->p1;
	Queue* nonempty = &obj->p2;
	if (!QueueEmpty(&obj->p1))
	{
		empty = &obj->p2;
		nonempty = &obj->p1;
	}

	return QueueBack(nonempty);
}

bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2);
}

void myStackFree(MyStack* obj) {
	Queue* empty = &obj->p1;
	Queue* nonempty = &obj->p2;
	if (!QueueEmpty(&obj->p1))
	{
		empty = &obj->p2;
		nonempty = &obj->p1;
	}
	QueueDestroy(nonempty);
	free(obj);
}